package cn.chen.数据结构.栈;

import java.util.ArrayList;
import java.util.Stack;


/**
 * 逆波兰计算器：
 *  使用的是后缀表达式
 * */
public class PolandNotation {

    public static void main(String[] args){

        String str = "  (4-2)*5+(1+20+3*5)-2 ";

        int result = getResult(getListString(toLast(str)));
        System.out.println(str+"="+result);
    }
    // 中缀表达式转成后缀表达式
    public static String toLast(String middle){

        // 创建两个栈
        Stack<String> s1=new Stack<>();
        Stack<String> s2=new Stack<>();

        StringBuilder sb=new StringBuilder();   // 线程不安全的，速度快
        //1、从左至右扫描字符串
        int index=0;
        while(true){

            if(index>middle.length()-1){
                if(sb.length()>0){  // 将最后一个数据添加到s2栈中，
                    s2.push(sb.toString());
                    sb.delete(0,sb.length());
                }
                break;
            }
            char c = middle.substring(index, index+1).charAt(0);
            index++;

            if(" ".equals(c+"")){   // 判断是否是空格

                continue;   // 是空格就跳出本次循环
            }

            // 判断是字符还是数字
            try{

                Integer.parseInt(c+""); // 如果不出现异常，就是数字
                sb.append(c);
            }
            catch (Exception e){    // (3-2)*5+(1+2)

                // 先将sb中的数字压入s2栈中
                if(sb.length()>0) {
                    s2.push(sb.toString());
                    sb.delete(0, sb.length());
                }

                if(s1.empty()){ // s1栈为空，直接将运算符压入栈中

                    s1.push(c+"");
                }
                else{

                    if("(".equals(c+"")){   // 该符号是（括号，直接压入栈中

                        s1.push(c+"");
                    }
                    else if(")".equals(c+"")){  // 该符号是)括号，弹出栈顶元素，直到弹出到(为止

                        while(!s1.peek().equals("(")){  // peek方法就是查看栈顶元素，但是不弹出栈顶元素

                            s2.push(s1.pop());  // 循环将不是(的运算符压入s2栈中，直到循环到(为止，
                        }
                        s1.pop();   // 将(括号删除掉。
                    }else{  // 该符号既不是（也不是），所以是运算符

                        String top = s1.peek();  // 获取栈顶元素,但是不出栈

                        if ("(".equals(top)) {    // 栈顶是（,所以直接将该运算符压入栈中

                            // 先将(压入栈中，因为这里的pop是弹出栈顶，所以要压回去
//                            s1.push(top);
                            s1.push(c + "");
                        } else {  // 栈顶不是(，所以就用栈顶与该运算符进行比较优先级

                            int cPro = priority(c); // 该运算符

                            while (true) {

                                int topPro = priority(top.charAt(0));   // 栈顶元素
                                if (topPro < cPro) {    // 将该运算符压入栈中

                                    s1.push(c + "");
                                    break;
                                } else {  // 将栈顶元素压入s2栈中

                                    s2.push(s1.pop());
                                    if (!s1.empty())
                                        top = s1.peek();
                                    else {
                                        s1.push(c + "");
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        while(!s1.empty()){ // 将s1中剩下的运算符压入s2中

            s2.push(s1.pop());
        }
        // 将s2中的元素压入s1栈中进行逆序，这样得到的就是正确的后缀表达式了
        while(!s2.empty()){ // 3 2 - 5 * 1 2 + +     s2 是这样

            s1.push(s2.pop());
            s1.push(",");
        }
        while (!s1.empty()) {   // 将s1中的遍历出来，组成字符串
            sb.append(s1.pop());
        }
        return sb.toString().substring(1,sb.length());  // 截取字符串， 将最后多余的空格给删除掉
    }

    // 判断运算符的优先级，程序员来定义的程序的优先级,数字越大，优先级越高
    public static int priority(int oper){

        if(oper=='+'|| oper == '-')
            return 0;
        if(oper == '*' || oper == '/')
            return 1;
        return -1;  // 这种就是其他符号就返回-1；
    }

    // 将字符串转成ArrayList
    public static ArrayList<String> getListString(String str){

        ArrayList<String> list=new ArrayList<>();
        String[] s = str.split(",");    // 使用空格分隔字符串
        for(String ss:s){

            list.add(ss);
        }
        return list;
    }
    // 参数ArrayList，配合Stack计算出结果
    public static int getResult(ArrayList<String> list){

        Stack<Integer> stack=new Stack<>();
        for(String s:list){

            // 这里通过字符串转换成int类型，是否成功来判断是否是数字
            try{
                // 该字符是数字
                int i = Integer.parseInt(s);
                stack.push(i);  // 将数字压入栈中
            }
            catch (Exception e){

                // 该字符是运算符 次顶元素 操作符 栈顶元素
                int num1=stack.pop();
                int num2=stack.pop();

                // 将两个数的计算结果压入栈中
                stack.push(cal(num1,num2,s.charAt(0)));
            }
        }
        return stack.pop();
    }
    // 计算结果
    public static int cal(int num1,int num2,char oper){

        int cal=0;
        switch (oper){

            case '+':
                cal=num1+num2;
                break;
            case '-':
                cal=num2-num1;  // 这里是num2-num1，因为num2是后出栈的，但是在表达式中是前面的
                break;
            case '*':
                cal=num1*num2;
                break;
            case '/':
                cal=num2/num1;
                break;
        }
        return cal;
    }
}
